LIBKAKY RESEARCH REPORTS ~mm NAVAL POSTGRADUATE SCH MONTEREY, CALIFORNIA 93i NPS-55-86-010 NAVAL POSTGRADUATE SCHOOL Monterey, California TECHNICAL DETERMINISTIC GRAPHICAL GAMES ALAN R. WASHBURN MAY 1986 Approved for public release: distribution unlimited FedDocs D 208.14/2 NPS-55-86-010 Prepared for: val Postgraduate School nterey, CA 93943-5000 . NAVAL POSTGRADUATE SCHOOL MONTEREY, CALIFORNIA Rear Admiral R. H. Shumaker D. A. Schrady Superintendent Provost Reproduction of all or part of this report is authorized. This report was prepared by: L XTiHirv m A^s.-n ATION O- 'H-S P^jt mP L EVKNOXUBKAHV REPORT DOCUMENTATION PAGE ^^LTOgTORADlWlg 8CHC MOWEREV CA WW34jff J"Rl ORT SECURITY CLASSlflCATION UNCLASSIFIED lb RESTRICTIVE MARKINGS a. SECURITY CLASSIFICATION AUTHORITY D DECLASSIFICATION /DOWNGRADING SCHEDULE j DISTRIBUTION/ AVAILABILITY OF REPORT Approved for public release; distribution unl imited. PERFORMING ORGANIZATION REPORT NUMBE R("s') NPS55-86-010 5 MONITORING ORGANIZATION REPORT NUMBER(S) j NAME OF PERFGRMiNU ORGANIZATION Naval Postgraduate School bD OFFICE SYMBOL (If applicable) Code 55 7d NAME OF MONITORING ORGANIZATION c. ADDRESS {City. State, and ZIP Code) Monterey, CA 93943-5000 7b. ADDRESS (dry. State, and ZIP Code) j, NAME OF FUNDING /SPONSORING ORGANIZATION 80 OFFICE SYMBOL (// applicable) 9 PROCUREMENT INSTRUMENT IDENTIFICATION NUMBER ADDRESS (City. State, and ZIP Code) 10 SOURCE OF FUNDING NUMBERS PROGRAM ELEMENT NO D ROJECT NO TASK NO. WORK UNIT ACCESSION NO Title (inciuae Security Classification) DETERMINISTIC GRAPHICAL GAMES ! PERSONAL AUTHOR(S) Washburn. Alan R. a. TYPE OF REPORT Technical 13b. TIME COVERED FROM TO 14. DATE OF REPORT (Year, Month, Day) 1986 Mav 15 PAGE COUNT 1-3 i SUPPLEMENTARY NOTATION COSATI CODES 18 SUBJECT TERMS (Continue on reverse it necessary and identify by block number) FIELD GROUP SUB-GROUP Game, Chess, Graph I ABSTRACT (Continue on reverse it necessary and identify by block numoer) This paper gives a simple algorithm for solving a class of graphical games where infinite play is possible. ) DISTRIBUTION/ AVAILABILITY OF ABSTRACT _GQuNCLASSlFlED/UNLlMlTED D SAME AS RPT D OTIC USERS 21 ABSTRACT SECURITY CLASSIFICATION UNCLASSIFIED a NAME OF RESPONSIBLE INDIVIDUAL Man R. Washburn M 22b TELEPHONE (include AreaCoae) 408-646-2381 22c OFFICE SYMBOL Code 55Ws 3 FORM 1473, aa mar BJ APR coition may be used until e/nausted All other editions are obsolete SECURITY CLASSIFICATION OF THIS PAGE DETERMINISTIC GRAPHICAL GAMES Abstract This paper gives a simple algorithm for solving a class of graphical games where infinite play is possible. Introduction A Deterministic Graphical (DG) game is a two person zero sum game played on a directed graph with n > nodes. Nodes are of two kinds: terminal and continuing. Terminal nodes are those with no successors, and have a payoff to player 1 associated with them. Continuing nodes have at least one successor, and are labelled to indicate which player chooses the successor. Play begins at some specified node, and continues until a terminal node is reached. If no terminal node is ever reached, the payoff is by convention 0. Our main intention in this paper is to describe an algorithm for solving DG games in o(n 3 ) steps. The reader may not welcome our introduction of a new term for what may seem like a familiar class of games. However, DG games are actually a slightly new topic. The deterministic Perfect Information games of von Neumann and Morgenstern (1944) and also Kuhn (1953) are restricted to be trees, which makes them a special case. It is true that DG games for which infinite play is impossible (tic-tac-toe is a good example) can always be put in the form of a tree by replicating nodes, but that operation can greatly increase the number of nodes. Besides, there are interesting DG games for which infinite play is possible. Chess is one of these; the FIDE rules (Harkness, 1956) permit a draw to be demanded in certain cases where no conclusion is in sight, but never force a draw merely on account of game length. The Perfect Information games of Berge (1957, 1962) are closer to DG games, but differ in that the payoff is influenced by all positions (nodes) encountered in play, rather than only the terminal node. Several authors have studied games similar to DG games where only two or three payoffs are possible (Zermelo (1912), Holladay (1957), Smith (1966)). Smith (1966) even comments that games with many possible payoffs are in principle solvable by any method that can solve games with only two. Nonetheless, the DG class has heretofore been nameless. DG games are interesting because they seem to be the largest class of "games of perfect information" that simultaneously permits parsimonious representation and efficient computation. The possibility of infinite play is explicit in DG games, even though the representation of a DG game is itself finite. This permits the parsimonious representation of games wherein a position can be repeated, without resort to devices such as move counters or additional rules that simply prohibit repetition. Introducing a large limit on the number of moves typically does not change the value of a game, but does have the effect of greatly expanding the number of nodes in its graphical representation. Pultr and Morris (1984) show that prohibiting repetitions complicates the computational problem in an essential way. The most natural thing to do in the presence of potentially infinite play seems to be to simply permit it, which is consistent with representation as a DG game. DG games are solvable in polynomial time in spite of the possibility of infinite play, as will be shown below. The fact that the payoff for infinite play in a DG game is assumed to be is not really restrictive, since the addition of any constant to all the payoffs of a game is strategically neutral. The assignment of payoff to infinite play is simply an analytical convenience. We now offer the following formal Definition : . A DG game is a directed graph with finitely many nodes partitioned into three sets: S 1 (S 2 ) is the set of nodes where player 1 (player 2) chooses the successor, and T is the set of terminal nodes on which some real payoff function F is defined. The successor function is r, with rx being empty if and only if xeT. Recursive Games and Solvability DG games are special cases of Recursive Games. Everett (1957) has therefore shown that all DG games have values, and, since the game element corresponding to each node has a trivial minimax solution, that optimal stationary strategies exist. Since the existence of stationary strategies is guaranteed, we will omit the word "stationary" in what follows. A strategy Oi for player 1 is then simply a choice of a successor node in Tx for each xeS^ to be used at every opportunity if x arises more than once. Strategies for player 2 are defined similarly. Definition : If H is some subset of the nodes of DG, we say that DG is solvable over H if there is a pair of strategies (a x ,a 2 ) and a real function W defined on the nodes of DG such that if the initial node is xeH, a) all successors of x will remain in H and the payoff will be at least Wx as long as player 1 employs a lf and b) all successors of x will remain in H and the payoff will be at most Wx as long as player 2 employs o 2 DG will be said to be solvable if it is solvable over all nodes. We wish to show that DG is solvable. Our method will be to show that DG is solvable over T, and that the set of nodes for which DG is solvable can always be expanded if it is incomplete. We will frequently take advantage of the fact that, if properties a) and b) above hold for an "initial" node xeH, they will also hold if node x is chosen any time before the game terminates; this follows from the stationarity of the strategies being considered. Preparatory Lemmas L emma 1 Suppose that DG is solvable over H, that T c H, and that there is some node yeH for which rye H. Then the game is solvable over HU ty}. Proof Let o lf o 2 > and W solve DG over H, and suppose yeS 1 . We will modify the strategies and extend W to include y, so that DG is solved over H {y}. The extension is Wy = max Wz ( 1 ) zeTy If z is any maximizing node in (1), let a/ be identical to afj except that player 1 maps y into z. Since o/ agrees with o x on H, o l * guarantees that all successors of nodes in H will remain in H, and therefore the same thing is true of nodes in Hij{y}. Furthermore, a x ' guarantees at least Wx for xeH {y}; any exception would contradict the fact that o x guarantees Wx for xeH. This establishes property a) for a l 1 and Hu(y). To establish property b) for o 2 and H u(y}, we have only to note that rye H, which guarantees that successors of y remain in Hu(y) (in H, in fact) regardless of the strategy employed by player 1, and also note that Wy is defined to be a maximum, which means that no payoff larger than Wy is possible from node y as long as player 2 employs o 2 . This completes the proof of lemma 1 for the case where yeS 1 . Since TcH, the only other possibility is that yeS 2 , in which case take Wy = min Wz (2) zeTy and define o 2 ' to be a 2 except that player 2 maps y into z. The rest of the proof is similar. Lemma 1 assumed the existence of a node yeH for which Tyc H. In the next lemma, we assume that such a node does not exist. Lemma 2 Suppose that DG is solvable over H, that TcH, and that H n ry is not empty for any yeH. Then there exists some yeH for which the game is solvable over Hu(y). Proof: Let o x , a 2 , W solve the game over H. Since by assumption each player has the option of mapping nodes in H into H, there are strategies Z x for player 1 and Z 2 for player 2 with the properties that l l (Z 2 ) agrees with Oi (o 2 ) on H and that Z x (Z 2 ) maps nodes in H into H . Furthermore, nodes in H are not successors of nodes in H under either o t or o 2 , and therefore Z lt £ 2 , W solves the game over H. Let Q. = {(x,i) xeHOS , ieHnrx}; j = 1,2 (3) J J and let w t = max Wi, and w 2 = min Wi. (4) (x.DeQj (x,i)eQ 2 If Qj (Q 2 ) is empty, let w t be any negative number (w 2 be any positive number). Intuitively, w 1 is the best payoff in H obtainable by player 1 from anywhere in H, and similarly for w 2 and player 2. We will prove the lemma in three cases. Case 1 (w^O) Let (y,z) be any maximizing pair in the definition of w x , let Wy = v 1 , and let o/ be a l except that o/ maps y into z. The proof that property a) holds for o/ and Hufy! is as in lemma 1. On the other hand player 2 can guarantee a payoff of at most Wy from y by employing £ 2 , since under that strategy the payoff will not exceed w, if some successor node (necessarily a choice of player 1) is in H, or (since H contains no terminal nodes) if all successor nodes are in H. Since E 2 agrees with a 2 on H, property b) holds for Z 2 and Hu{y}. Therefore a/, Z 2 > w solves G over Hu{y}. Case 2 (w 2 ^0) Let (y,z) be any minimizing pair in the definition of w 2 , let Wy = w 2 , and let o 2 ' be a 2 except that o 2 ' maps y into z. Then Z l , o 2 '» W solves G over H^ {y}. The proof is similar to that of case 1. Case 3 (w^O and w 2 >0) In this case we can take Wy = for all y in H. £, , E 2 , W solves DG over all nodes. Note that Z 1 guarantees at least from any node yeH because a) If player 2 employs any strategy for which some successor of y is in H, o x and therefore l x guarantees a non-negative payoff. b) If player 2 employs any strategy for which no successor of y is in H, Z 1 guarantees a payoff of 0. Similarly, E 2 guarantees a payoff of at most from any node in H, and this completes the proof of Case 3 and Lemma 2. DG Theorem All DG games are solvable. Proof: Let H = T, and Wx = Fx for xeT. Any DG game is evidently solvable over H . If H does not include all nodes, either lemma 1 or lemma 2 applies, and hence the game is solvable over some set H x that strictly includes H . In a similar manner we can generate H 2 , H 3 , etc. Since there are only finitely many nodes, we must eventually encounter some H that includes all nodes, which means that the game is solvable. An Example Figure 1 shows the solution of a DG game with 18 nodes. Squares represent moves for the maximizer, and circles for the minimizer. All arcs are oriented toward the right except for the two that are curved, which are oriented to the left. The terminal nodes are marked with numbers that CD CD Q O .— CO ZD CD o oo indicate the payoff. The five non-terminal nodes from which the value is non-zero have letter labels to indicate the order of computation. Lemma 1 applies to nodes a,b,c, and e, and case 1 of lemma 2 applies to node d. Case 3 of lemma 2 applies to the other four nodes, which are the last nodes to enter H and the ones from which optimal play is non-terminating. Computational Considerations A bound on the computational effort required for a DG game with n nodes can be obtained by first observing that the essential operation in applying either lemma 1 or 2 is that of comparing two values, one of which has a node index. Let h be the number of nodes in the solved set H. A straightforward implementation of the DG Theorem would involve a loop in which h is incremented by one in every cycle until either case 3 of lemma 2 arises or else h=n , whichever comes first. In the worst case, one would have to do a comparison for every pair (x,y) where xeH and yeH, a total of h(n-h) comparisons when the loop index is h. Summing on h , we obtain a bound of n n 1 h(n^h) comparisons, which is approximately f h(n-h)dh=n 3 /6. The amount h=0 of effort involved is therefore no worse than cubic in the number of nodes. The n 3 /6 bound would presumably not be sharp for a careful implementation of the DG Theorem, since making h(n-h) comparisons may very well permit the addition of multiple nodes to H (all nodes x in H for which Tx H can be added to H, for example), and other efficiencies are also possible. Random Moves There is no conceptual difficulty in introducing random moves into graphical games. If finite, such games are still Recursive Games and therefore have solutions with stationary strategies. However, the inclusion of random moves seems to complicate the solution procedure in an essential manner; there is apparently no feature to exploit that is not already present in Recursive Games. This is the reason for excluding the possibility of random moves in DG games. There are thus two classes of graphical games for which a simple solution technique is available, DG games being one and finite tree games (possibly with random moves) being the other. Backgammon is an example of a game that lies in neither class. In Practice We have argued that DG games permit a parsimonious representation of games such as Chess. It is clear that even a parsimonious representation and a polynomial time algorithm will not help much in solving games as complicated as the archtype, however. Without taking advantage of symmetry, even the representation of tic-tac-toe as a DG game would be a formidable task. The French Military Game (Gardner (1963.), Lucas (1895)) comes to mind as an example of a non-trival parlor game solvable as a practical matter if a determined practioner were to make repeated application of lemmas 1 and 2. The main difficulty with parlor games is the work involved in translating the rules into graphical notation, rather than the ensuing computations. For large DG games expressed directly as graphs, the existence of a polynomial time solution algorithm would be more significant. 10 References Berge, C, Topological Games with Perfect Information, Contributions to the Theory of Games, vol _3_, Princeton U. Press, Princeton, NJ, 1957, pp 165-178. Berge, C, The Theory of Graphs, Methuen and Co. Ltd., London, 1962. Everett, H., Recursive Games, Contributions to the Theory of Games , vol 3, Princeton U. Press, Princeton, NJ, 1957, pp 47-78. Gardner, M., Mathematical Games, Scientific American, October 1963, pp 1 24-1 26. Harkness, K., The Official Blue Book and Encyclopedia of Chess , David McKay, New York, 1956. Holladay, J. C, Cartesian Products of Termination Games, Contributions to the Theory of Games , vol 3, Princeton U. Press, Princeton, NY, 1957, pp 189-200. Kuhn , H. W., Extensive Games and the Problem of Information, Contributions to the Theory of Games , vol 2, Princeton U. Press, Princeton, NJ, 1953, PP 193-216. Lucas, M. E. , Recreations Mathematiques , vol 3, Gauthier-Villars , Paris, 1895, pp 105-1 1 6. Pultr, A., and F. L. Morris, Prohibiting Repetitions Makes Playing Games Substantially Harder, Int. Journal of Game Theory 1 3 , 1984, pp 27-40. Smith, C. A. B. , Graphs and Composite Games, Journal of Comb. Theory 1_, 1966 pp 51-81. von Neumann, J., and 0. Morgenstern, Theory of Games and Economic Behaviour , Princeton U. Press, Princeton, NJ, 1944. Zermelo, E. , Uber Eine Anwendung Der Mengenlehre Auf Die Theorie Des Schachspiels. International Congress of Mathematicians, 5th, Cambridge University Press, 1912. 1 1 DISTRIBUTION LIST Professor F. L. Morris School of Computer and Information Sciences 313 Link Hall Syracuse University Syracuse, NY 1 3210 Professor Martin Shubik Cowles Foundation Yale University New Haven, CT 06520 Professor Guillermo Owen (Code 530n) Mathematics Department Naval Postgraduate School Monterey, CA 939^3-5000 Library (Code 01 42) Naval Postgraduate School Monterey, CA 939^3-5000 Dr. Ales Pultr Department of Mathematics Charles University Sokolovska 83, Prague 8 CZECHOSLOVAKIA Professor Matthew J. Sobel College of Management Georgia Instute of Technology Atlanta, GA 30332 Professor Lyn Thomas University of Edinburgh Department of Business Studies William Robertson Bldg. 50 George Square Edinburgh EH895Y UNITED KINGDOM Professor Jerzy Filar Mathematical Science Department John Hopkins University Baltimore, MD 21 218 12 Professor Alan Goldman 1 Mathematics Sciences Department John Hopkins University Baltimore, MD 21218 Professor William F. Lucas 1 1598 Beloit Claremont, CA 9171 1 Professor David Blackwell 1 Statistical Laboratory University of California - Berkeley Berkeley, CA 9^720 Professor A. J. Jones 1 Department of Mathematics Royal Holloway College University of London UNITED KINGDOM Research Administration (Code 012) 1 Naval Postgraduate School Monterey, CA 939^3-5000 Professor Alan R. Washburn (Code 55Ws) 10 Department of Operations Research Naval Postgraduate School Monterey, CA 939^3-5000 Center for Naval Analyses 1 2000 Beauregard Street Alexandria, VA 2231 1 Operations Research Center, Room E40-1 64 1 Massachusetts Institute of Technology Attn: R. C. Larson and J. F. Shapiro Cambridge, MA 02139 Defense Technical Information Center 2 Cameron Station Alexandria, VA 22314 13 DUDLEY KNOX LIBRARY 3 2768 00336440 7